package Leetcode;

import base.TreeNode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * 给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。
 *
 * @Author piper
 * @Date 2019/10/29 9:53 上午
 */
public class 力扣102_二叉树的层序遍历 {
    static List<List<Integer>> levels = new ArrayList<>();

    static List<List<Integer>> levelOrder1(TreeNode root) {
        if (root == null) return null;
        helper(root, 0);
        return levels;
    }

    static void helper(TreeNode t, int level) {
        if (levels.size() == level) {
            levels.add(new ArrayList<>());
        }

        levels.get(level).add(t.val);

        if (t.left != null) {
            helper(t.left, level + 1);
        }
        if (t.right != null) {
            helper(t.right, level + 1);
        }
    }

    static List<List<Integer>> levelOrder2(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        int level = 0;

        while (!queue.isEmpty()) {
            levels.add(new ArrayList<>());
            int size = queue.size();

            for (int i = 0; i < size; i++) {
                TreeNode node = queue.remove();
                levels.get(level).add(node.val);
                if (node.left != null) {
                    queue.add(node.left);
                }
                if (node.right != null) {
                    queue.add(node.right);
                }
            }
            level++;
        }

        return levels;
    }

    public static void main(String[] args) {
        TreeNode a = new TreeNode(1);
        TreeNode b = new TreeNode(2);
        TreeNode c = new TreeNode(3);
        TreeNode d = new TreeNode(4);
        TreeNode e = new TreeNode(5);
        TreeNode f = new TreeNode(6);
        TreeNode g = new TreeNode(7);

        a.left = b;
        a.right = c;
        b.left = d;
        b.right = e;
        c.left = f;
        c.right = g;

        levelOrder2(a);

        System.out.println(levels.toString());
    }

}
